package com.leetcode;

import com.leetcode.common.TreeNode;

/**
 * 437. 路径总和 III
 * 深度优先搜索
 * 自底向上
 *
 * @author fy
 * @date 2022/4/25 17:17
 */
public class Solution437_1 {

    public int pathSum(TreeNode root, int targetSum) {
        if (root == null) {
            return 0;
        }
        // 包含当前节点
        int res = rootSum(root, targetSum);
        // 不包含当前节点, 分别从当前节点的左右子节点开始
        res += pathSum(root.left, targetSum);
        res += pathSum(root.right, targetSum);
        return res;
    }

    /**
     * 包含当前节点并开始一直递归向下遍历
     *
     * @param node
     * @param targetSum
     * @return
     */
    private int rootSum(TreeNode node, int targetSum) {
        int res = 0;
        if (node == null) {
            return res;
        }
        if (node.val == targetSum) {
            res++;
        }
        res += rootSum(node.left, targetSum - node.val);
        res += rootSum(node.right, targetSum -node.val);
        return res;
    }

}
